﻿#include "排序.h"

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "栈.h"
#include "链表.h"
#include "队列.h"

void 插入排序(顺序表_结构* 表)
{
    const int 表长 = 表 -> 表长;
    int *数据 = 表->数据;
    for (int i = 1;i < 表长;i++)//数组从1开始遍历到n
    {
        const int 临时 = 数据[i];//当前要插入已排序数组中的元素
        //遍历已排序好的部分数组将未排序的首个元素插入到已排序好的数组中
        for (int j = i - 1;j >= 0;j--)
        {
            //遇到比要插入的数据大的数据时就将该数据后移放入要插入的元素
            if(数据[j] > 临时)
            {
                数据[j + 1] = 数据[j];
                数据[j] = 临时;
            }
            else
            {
                //一直移动到已排序的数据比要插入的数据小时，则本次插入结束退出循环
                break;
            }
        }
    }
}

void 冒泡排序(顺序表_结构* 表)
{
    const int 表长 = 表->表长;
    int *数据 = 表->数据;
    
    for (int i = 0;i < 表长;i++)
    {
        bool 是否交换了 = false;
        for (int j = 1;j < 表长-i;j++)
        {
            if(数据[j-1] > 数据[j])
            {
                是否交换了 = true;
                const int 临时 = 数据[j-1];
                数据[j-1] = 数据[j];
                数据[j] = 临时;
            }
        }
        if(!是否交换了)
        {
            break;
        }
    }
}

void 选择排序(顺序表_结构* 表)
{
    const int 表长 = 表->表长;
    int *数据 = 表->数据;
    for (int i = 0;i < 表长;i++)
    {
        int 最小 = 数据[i];
        int 最小索引 = i;
        //找到最小的数据和数据的索引
        for(int j = i+1;j < 表长;j++)
        {
            if(最小 > 数据[j])
            {
                最小 = 数据[j];
                最小索引 = j;
            }
        }
        //交换当前遍历的位置和存储最小值位置的值
        数据[最小索引] = 数据[i];
        数据[i] = 最小;
    }
}

int 折半查找合适的索引(const 顺序表_结构* 表,const int 终, const int 值)
{
    int 首 = 0;
    int 尾 = 终;
    const int *数据 = 表->数据;

    if(终 == 0)
    {
        return 数据[0] > 值 ? 0 : 1;
    }
    if(终 == 1)
    {
        if(数据[0] > 值)
        {
            return 0;
        }
        if(数据[1] > 值)
        {
            return 1;
        }
        return 2;
    }
    判断在区间:
    const int 中 = (首+尾)/2;
    
    if(数据[中] <= 值 && 值 <= 数据[中+1])
    {
        return 中 + 1;
    }
    
    if(数据[中-1] <= 值 && 值 <= 数据[中])
    {
        return 中;
    }
    
    if(值 <= 数据[中])
    {
        尾 = 中 - 1;
        if(尾 <= 首)
        {
            return 0;
        }
    }
    else
    {
        首 = 中 + 1;
        if(首 >= 尾)
        {
            return 终 + 1;
        }
    }
    
    
    goto 判断在区间;
}

void 折半插入排序(顺序表_结构* 表)
{
    const int 表长 = 表 -> 表长;
    int *数据 = 表->数据;
    for (int i = 1;i < 表长;i++)//数组从1开始遍历到n
    {
        const int 插 = 数据[i];//当前要插入已排序数组中的元素
        const int 排序好的索引 = i - 1;
        const int 要插入的索引 = 折半查找合适的索引(表,排序好的索引,插);
        //要插入的索引后面的元素依次后移
        for (int j = 排序好的索引;j >= 要插入的索引;j--)
        {
            数据[j+1] = 数据[j];
        }
        数据[要插入的索引] = 插;
    }
}

void 选择三个数的中值并将其放到值1(int *值1,int *值2,int *值3)
{
    const int 临时 = *值1;
    //值1是最小值 交换值2和值3中比较小的
    if(*值1 < *值2 && *值1 < *值3)
    {
        if(*值2 < *值3)
        {
            *值1 = *值2;
            *值2 = 临时;
        }
        else
        {
            *值1 = *值3;
            *值3 = 临时;
        }
        return;
    }
    //值1是最大值 交换值2和值3中比较大的
    if(值1 > 值2 && 值1 > 值3)
    {
        if(*值2 < *值3)
        {
            *值1 = *值3;
            *值3 = 临时;
        }
        else
        {
            *值1 = *值2;
            *值2 = 临时;
        }
    }
    //值1就是中间值不用交换
}
void 快速排序(int *数组, const int 首, const int 尾,int *递归深度,int *递归深度计数)
{
    if(首 >= 尾)
    {
        return;
    }
    选择三个数的中值并将其放到值1(&数组[首],&数组[(首+尾)/2],&数组[尾]);
    const int 中值 = 数组[首];//存储了中值的变量，则数组中，中值的位置可以视为空位
    
    int 首计数 = 首;
    int 尾计数 = 尾;
    
    while (首计数 < 尾计数)
    {
        //数组首部有空位先从尾部查找比中值小的放到空位
        while (首计数 < 尾计数 && 数组[尾计数] > 中值)
        {
            尾计数--;
        }
        if(首计数 < 尾计数)
        {
            //将末尾比中值小的数插到数组前面的空位上
            数组[首计数] = 数组[尾计数];
            首计数++;//插入后这个空位将不是空位
        }
        
        //插入到空位后数组的尾部可视为空位，从首部查找比中值大的放到空位
        while (首计数 < 尾计数 && 数组[首计数] < 中值)
        {
            首计数++;
        }
        if(首计数 < 尾计数)
        {
            //将数组首部比中值大的值放到尾部的空位上
            数组[尾计数] = 数组[首计数];
            尾计数--;//插入后这个空位将不是空位
        }
    }
    数组[首计数] = 中值;//当首计数和尾计数重合时重合的位置仍为空位，则放入存储的中值
    
    (*递归深度计数)++;
    *递归深度 = max(*递归深度,*递归深度计数);
    快速排序(数组,首,首计数-1,递归深度,递归深度计数);
    快速排序(数组,首计数+1,尾,递归深度,递归深度计数);
    (*递归深度计数)--;
}

定义 结构体
{
    int 左首,左尾,右首,右尾;
}快速排序切片_结构;

void 入栈快速排序切片(栈_结构 *栈, const 快速排序切片_结构 切片)
{
    数据入栈(栈,切片.右尾);
    数据入栈(栈,切片.右首);
    数据入栈(栈,切片.左尾);
    数据入栈(栈,切片.左首);
}

快速排序切片_结构 出栈快速排序切片(栈_结构 *栈)
{
    快速排序切片_结构 切片;
    切片.左首 = 数据出栈(栈);
    切片.左尾 = 数据出栈(栈);
    切片.右首 = 数据出栈(栈);
    切片.右尾 = 数据出栈(栈);
    return 切片;
}
//返回分组后的切片 中值已插入到数据表中
快速排序切片_结构 非递归快速排序左右分组(int *数组,const int 首,const int 尾)
{
    选择三个数的中值并将其放到值1(&数组[首],&数组[(首+尾)/2],&数组[尾]);
    const int 中值 = 数组[首];//存储了中值的变量，则数组中，中值的位置可以视为空位

    int 首计数 = 首;
    int 尾计数 = 尾;
    
    while (首计数 < 尾计数)
    {
        //数组首部有空位先从尾部查找比中值小的放到空位
        while (首计数 < 尾计数 && 数组[尾计数] > 中值)
        {
            尾计数--;
        }
        if(首计数 < 尾计数)
        {
            //将末尾比中值小的数插到数组前面的空位上
            数组[首计数] = 数组[尾计数];
            首计数++;//插入后这个空位将不是空位
        }
        
        //插入到空位后数组的尾部可视为空位，从首部查找比中值大的放到空位
        while (首计数 < 尾计数 && 数组[首计数] < 中值)
        {
            首计数++;
        }
        if(首计数 < 尾计数)
        {
            //将数组首部比中值大的值放到尾部的空位上
            数组[尾计数] = 数组[首计数];
            尾计数--;//插入后这个空位将不是空位
        }
    }
    数组[首计数] = 中值;//当首计数和尾计数重合时重合的位置仍为空位，则放入存储的中值
    
    快速排序切片_结构 分片;
    分片.左首 = 首;
    分片.左尾 = 首计数-1;
    分片.右首 = 首计数+1;
    分片.右尾 = 尾;
    return 分片;
}

void 非递归快速排序(顺序表_结构* 表)
{
    栈_结构 *分片栈 = 构造_栈();
    快速排序切片_结构 分片 = 非递归快速排序左右分组(表->数据,0,表->表长-1);
    入栈快速排序切片(分片栈,分片);
    do
    {
        const 快速排序切片_结构 栈顶分片 = 出栈快速排序切片(分片栈);
        
        if(栈顶分片.左首 < 栈顶分片.左尾)
        {
            分片 = 非递归快速排序左右分组(表->数据,栈顶分片.左首,栈顶分片.左尾);
            入栈快速排序切片(分片栈,分片);
        }
        if(栈顶分片.右首 < 栈顶分片.右尾)
        {
            分片 = 非递归快速排序左右分组(表->数据,栈顶分片.右首,栈顶分片.右尾);
            入栈快速排序切片(分片栈,分片);
        }
    }
    while (!栈空了(分片栈));
}

定义 结构体
{
    顺序表_结构 *左表;
    顺序表_结构 *右表;
}归并切片_结构;

void 归并排序(顺序表_结构 *表)
{
    const int *数据 = 表->数据;
    const int 长 = 表->表长;
    int 切片数 = ceilf((float)长 / 2);
    归并切片_结构 *切片 = calloc(切片数,sizeof(归并切片_结构));
    for(int i = 0;i < 切片数;i++)
    {
        切片[i].左表 = 构造_顺序表();
        切片[i].右表 = 构造_顺序表();
        添加顺序表数据(切片[i].左表,数据[2 * i]);
        if(2 * i + 1 < 长)
        {
            添加顺序表数据(切片[i].右表,数据[2 * i + 1]);
        }
    }

    判断归并结束:
    if(切片数 == 1)
    {
        顺序表_结构 *合并 = 合并两个升序顺序表(切片[0].左表,切片[0].右表);
        清空顺序表(表);
        for (int i = 0;i < 合并->表长;i++)
        {
            添加顺序表数据(表,查询顺序表数据(合并,i));
        }
        free(合并);
        return;
    }

    const int 合并切片数 = ceilf((float)切片数 / 2);
    归并切片_结构 *合并切片 = calloc(合并切片数,sizeof(归并切片_结构));
    
    for(int i = 0;i < 合并切片数;i++)
    {
        顺序表_结构 *左表1 = 切片[2*i].左表;
        顺序表_结构 *左表2 = 切片[2*i].右表;
        合并切片[i].左表 = 合并两个升序顺序表(左表1,左表2);
        free(左表1);
        free(左表2);
        
        if(2*i+1 < 切片数)
        {
            顺序表_结构 *右表1 = 切片[2*i+1].左表;
            顺序表_结构 *右表2 = 切片[2*i+1].右表;
            合并切片[i].右表 = 合并两个升序顺序表(右表1,右表2);
            
            free(右表1);
            free(右表2);
        }
        else
        {
            合并切片[i].右表 = 构造_顺序表();
        }
        
    }
    free(切片);
    切片 = 合并切片;
    切片数 = 合并切片数;
    goto 判断归并结束;
}

int 获取位数(const int 数, const int 位)
{
    const int 除以 = powf(10,位);
    return 数/除以%10;
}

void 基数排序(顺序表_结构* 表, const int 最大位数)
{
    链表_结构* 十个桶[10];
    for (int i = 0;i < 10;i++)
    {
        十个桶[i] = 构造_链表();
    }
    const int *数据 = 表->数据;
    const int 表长 = 表->表长;
    
    for (int 位 = 0;位 < 最大位数;位++)
    {
        //数据入桶
        for (int i = 0;i < 表长;i++)
        {
            const int 位数 = 获取位数(数据[i],位);
            添加链表数据(十个桶[位数],数据[i]);
        }
        清空顺序表(表);
        //数据回收
        for (int i = 0;i < 10;i++)
        {
            链表节点_结构 *遍历节点 = 十个桶[i]->第一个节点;
            while (遍历节点 != NULL)
            {
                添加顺序表数据(表,遍历节点->数据);
                遍历节点 = 遍历节点->后继;
            }
            清空链表(十个桶[i]);
        }
    }
    
    //销毁链表
    for (int i = 0;i < 10;i++)
    {
        销毁_链表(十个桶[i]);
    }
}
